public class isMatch {
    public boolean _isMatch(String s, String p) {
        if (p.length() == 0)
            return s.length() == 0;

        int s_len = s.length();
        int p_len = p.length();
        // 我们用 f[i][j] 表示 s 的前 i 个字符与 p 中的前 j 个字符是否能够匹配。
        boolean[][] dp = new boolean[s_len + 1][p_len + 1];
        // 初始化
        dp[0][0] = true;
        // 第一行 s="", p="a*", *前面必有字母，代表匹配0次才能是 true,其他情况都是false
        for (int i = 2; i <= p_len; i += 2) {
            dp[0][i] = dp[0][i - 2] && p.charAt(i - 1) == '*';
        }
        // 第一列, 除了dp[0][0]外，其他都是false

        // 初始化第一行 s="" , p=p
        for (int i = 1; i <= s_len; i++) {// 行
            for (int j = 1; j <= p_len; j++) {
                if (p.charAt(j - 1) == '*') {
                    // 匹配0次
                    if (j >= 2) {
                        dp[i][j] = dp[i][j - 2];
                    }
                    // 匹配多次,看如s=aa p=a*或p = .*
                    if (i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
                        dp[i][j] = dp[i][j] || dp[i - 1][j];
                    }

                } else if (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                }

            }

        }
        return dp[s_len][p_len];
    }
}
